package org.bgee.psp4jdbc.pool;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Map;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.atomic.AtomicInteger;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

/**
 * The aim of this class is to store {@link PoolElement}s associated with a key, 
 * and to keep them sorted by the order they entered in the <code>Pool</code>.
 * <p>
 * It is made of the combination of a <code>ConcurrentHashMap</code> and
 * a <code>ConcurrentLinkedDeque</code>. 
 * It has a maximum size which triggers an automatic removal of an element 
 * (using either LRU or LFU algorithm) when reached.
 * <p>
 * This <code>Pool</code> is made of <code>java.util.concurrent</code> classes, 
 * and thus has a guarantee of happens-before relation between threads. 
 * It does not offer a guarantee of atomicity of the operations, 
 * as its methods are unlikely to be called by different threads at a same time, 
 * but rather, should be used successively by different threads.
 * 
 * @author Frederic Bastian
 * @author Mathieu Seppey
 * @version 1, August 2013
 * @see PoolMonitor
 * @see PoolElement
 * @since 1
 */
public class Pool
{
	/**
	 * Eviction methods available when an element needs to be removed from a pool 
	 * because the maximum capacity is reached: 
	 * <ul>
	 * <li><code>LRU</code>: Least Recently Used.
	 * <li><code>LFU</code>: Least Frequently Used.
	 * </ul>
	 */
	public enum EvictionMethod {
		LRU(), LFU();
	}
    /**
     * <code>Logger</code> of the class. 
     */
    private final static Logger log = LogManager.getLogger(Pool.class.getName());

    /**
     * A concurrent <code>Map</code> to store <code>PoolElement</code>s 
     * not currently under use, associated to their id (see {@link PoolElement#getId()}).
     */
    private final ConcurrentMap<String, PoolElement> poolContent;
    /**
     * An <code>AtomicInteger</code> to keep track of the number of <code>PoolElement</code> 
     * in this <code>Pool</code>. We do not rely on the size of {@link #poolContent}, 
     * because a <code>PoolElement</code> can be added to {@link #poolContent} 
     * before being fully added to this <code>Pool</code>.
     */
    private final AtomicInteger elementCount;

    /**
     * A <code>ConcurrentNavigableMap</code> that associate <code>PoolElement</code>s 
     * as values, to <code>Integer</code>s as keys that represent the sequence index 
     * of use of the corresponding <code>PoolElement</code>. This sequence index is 
     * such as a <code>PoolElement</code> more recently used will have a greater 
     * sequence index than a <code>PoolElement</code> less recently used. 
     * See {@link PoolElement#getUseSequence()}.
     * <p>
     * We do not use a <code>LinkedHashMap</code> using the constructor 
     * {@link java.util.LinkedHashMap#LinkedHashMap(int, float, boolean)} allowing 
     * to use a LRU access order, because there is no concurrent <code>LinkedHashMap</code>.
     * We also do not use a <code>ConcurrentLinkedDeque</code> because of the increased 
     * complexity for a remove operation (and also because it is not available in Java 6).
     */
    private final ConcurrentNavigableMap<Integer, PoolElement> lruOrder;
    /**
     * A concurrent <code>NavigableMap</code> ordering the <code>PoolElement</code>s 
     * based on their number of use, for LFU eviction, corresponding to the associated 
     * {@link PoolElement#getUseCount()}. 
     * <p>
     * As several keys can be associated to a same number of use, values of this 
     * <code>NavigableMap</code> are ConcurrentNavigableMap<Integer, PoolElement>, 
     * functioning exactly as {@link #lruOrder}, so that in case of equality 
     * a LRU eviction is used.
     */
    private final ConcurrentNavigableMap<Integer, 
        ConcurrentNavigableMap<Integer, PoolElement>> lfuOrder;

    /**
     * an <code>int</code> which contains the maximum size of the <code>Pool</code>.
     */
    private final int maxSize;
    /**
     * The <code>EvictionMethod</code> to use when {@link #triggerEviction()} is called.
     * @see #evictionFactor
     */
    private final EvictionMethod evictionMethod;
    
    /**
     * A <code>float</code> defining the proportion of <code>PoolElement</code>s 
     * present in this <code>Pool</code> that should be evicted 
     * when {@link #triggerEviction()} is called.
     * @see #evictionMethod
     */
    private final float evictionFactor;

    /**
     * Constructor that initializes the maximum size and eviction method.
     * 
     * @param size		an <code>int</code> representing the maximum size 
     * 					of this <code>Pool</code>.
     * @param method 	the <code>EvictionMethod</code> to use when the maximum capacity 
     * 					is reached and an eviction triggered. 
     * @param evictionFactor A <code>float</code> defining the proportion of 
     * 						<code>PoolElement</code>s present in this <code>Pool</code> 
     * 						that should be evicted when an eviction is triggered.
     */
    public Pool(int size, EvictionMethod method, float evictionFactor)
    {
    	log.entry(size, method, evictionFactor);
        this.poolContent = new ConcurrentHashMap<String, PoolElement>();
        this.elementCount = new AtomicInteger(0);
        this.lruOrder = new ConcurrentSkipListMap<Integer, PoolElement>();
        this.lfuOrder = new ConcurrentSkipListMap<Integer, 
        		ConcurrentNavigableMap<Integer, PoolElement>>();
        this.maxSize = size;
        this.evictionMethod = method;
        this.evictionFactor = evictionFactor;
        log.exit();
    }

    /**
     * Remove the <code>PoolElement</code> associated to <code>key</code> 
     * from this <code>Pool</code>, return it, and report the new state of the pool 
     * to the <code>PoolMonitor</code>.
     * 
     * @param key 	the key that matches the <code>PoolElement</code> to be removed.
     * @return 		the removed <code>PoolElement</code>, or <code>null</code> 
     * 				if nothing was removed.
     */
    public PoolElement remove(String key) {
    	log.entry(key);
    	
        PoolElement element = this.poolContent.remove(key);
        if (element != null) {
            this.remove(element);
        }
        return log.exit(element);
    }
    
    /**
     * Remove <code>element</code> from this <code>Pool</code>, if it is present 
     * associated to <code>key</code>. If <code>element</code> is found 
     * associated to <code>key</code> and removed, this method returns <code>true</code>, 
     * and report the new state of the pool to the <code>PoolMonitor</code>. 
     * Otherwise, returns <code>false</code>.
     * 
     * @param key 		the key that matches the <code>PoolElement</code> to be removed.
     * @param element	the <code>PoolElement</code> to be removed if associated to 
     * 					<code>key</code>.
     * @return 			<code>true</code> if <code>element</code> was removed.
     */
    public boolean remove(String key, PoolElement element) {
    	log.entry(key, element);
    	
        if (this.poolContent.remove(key, element)) {
            this.remove(element);
            return log.exit(true);
        }
        return log.exit(false);
    }
    
    /**
     * Method to perform all operations necessary to remove an <code>element</code> 
     * from this <code>Pool</code>, except removing it from {@link #poolContent} 
     * (this is done by {@link #remove(String)} or {@link #remove(String, PoolElement)}).
     * 
     * @param element 	The <code>PoolElement</code> to remove from this <code>Pool</code>.
     */
    private void remove(PoolElement element) {
    	log.entry(element);
    	log.debug("Take from the pool the element matching the key {}", element.getId());
        //remove the element from the LFU and LRU collections
        //let's add a bit of atomicity here
        synchronized(element) {
        	
        	//*************************
    		//  LFU MECHANISM
    		//*************************
        	if (this.evictionMethod.equals(EvictionMethod.LFU)) {
        		ConcurrentNavigableMap<Integer, PoolElement> sameFreqElements = 
        				this.lfuOrder.get(element.getUseCount());
        		if (sameFreqElements != null && 
        				sameFreqElements.remove(element.getUseSequence(), element)) {
        			//if no more Pools are associated to that use frequency, 
        			//remove the Map from lfuOrder.
        			//synchronized on this Map so that no element can be added to it 
        			//before we remove it from lfuOrder
        			if(sameFreqElements.isEmpty()) {
        				synchronized(sameFreqElements) {
        					if(sameFreqElements.isEmpty()){
        						this.lfuOrder.remove(element.getUseCount());
        					}
        				}
        			}
        		} else {
        			throw log.throwing(new IllegalStateException(
        					"A PoolElement reported an incorrect use frequency and " +
        							"could not be located. PoolElement causing the error reported " +
        							"a use count of " + element.getUseCount()));
        		}
        	}
        	//*************************
    		//  LRU MECHANISM (needed also for LFU frequency queues)
        	//we need to do it after removing element from LFU frequency queue, 
        	//otherwise another PoolElement could acquire the same frequencyCount meanwhile
    		//*************************
        	if (!this.lruOrder.remove(element.getUseSequence(), element)) {
        		throw log.throwing(new IllegalStateException(
        				"A PoolElement stored in a Pool was in an improper state, " +
        				"could not find the use sequence " + element.getUseSequence()));
        	}
        }
        log.trace("Trying to notify PoolMonitor");
        //notify the PoolMonitor
        try {
        	log.trace("Notifying PoolMonitor: {} - {} - {}", this, this.elementCount.get(), -1);
			PoolMonitor.updatePoolSize(this, this.elementCount.getAndDecrement(), -1);
			log.trace("PoolMonitor notified, current pool: {}", this);
		} catch (ReleaseException e) {
			//this Exception is supposed to happen only when trying to release 
			//a PoolElement, if we reached the overall maximum capacity. 
			//we are going to assume that it will never happen when *decreasing*
			//the pool size, and throw an Error instead, not to be caught.
			throw log.throwing(new Error(e));
		}
        log.exit();
    }

    /**
     * Get the number of pooled elements in this <code>Pool</code>.
     * 
     * @return an <code>int</code> representing the number of pooled elements
     */
    protected int size(){
        return this.elementCount.get();
    }

    /**
     * Add <code>element</code> to this <code>Pool</code>, associated with its ID as key,
     * only if the key is not already present: if two <code>PoolElement</code> 
     * instances have a same ID, it means there are equivalent, see {@link PoolElement#getId()}.
     * If <code>element</code> was actually added, this method also reports 
     * the new state of the pool to the <code>PoolMonitor</code>. 
     * <p>
     * If this <code>Pool</code> reached its maximum capacity, the eviction mechanism 
     * is triggered. 
     * 
     * @param element	the <code>PoolElement</code> to be associated with its ID 
     * 					(see {@link PoolElement#getId()}). 
     * @return 		the previous value associated with the ID of <code>element</code> 
     * 				(see {@link PoolElement#getId()}), or <code>null</code> if there was 
     * 				no mapping corresponding to its ID.
     * @throws IllegalArgumentException	If the provided <code>PoolElement</code> 
     * 									was already released, and should not be pooled 
     * 									anymore.
     * @throws ReleaseException 		if an error occurred while evicting a 
     * 									<code>poolElement</code> if the pool has reached 
     * 									its maximum capacity.
     */
    public PoolElement putIfAbsent(PoolElement element) 
    		throws IllegalArgumentException, ReleaseException {
    	log.entry(element);
    	if (element.isReleased()) {
    		throw log.throwing(new IllegalArgumentException("The PoolElement " + element + 
    				" has already been released and should not be pooled anymore."));
    	}

    	//need some atomicity, as values corresponding to this PoolElement 
    	//will be added to several Collections, but could be modified meanwhile.
		//Synchronizing on this element should not impact other threads badly.
    	synchronized(element) {
    		PoolElement previousValue = 
    				this.poolContent.putIfAbsent(element.getId(), element);
    		if (previousValue != null) {
    			return log.exit(previousValue);
    		}
    		log.debug("Insertion into the pool of the element {} for key {}", 
    				element, element.getId());
    		
    		//if adding an element would make the pool to exceed its maximum capacity, 
    		//trigger the eviction mechanism before adding element to the LFU and LRU queues. 
    		if (this.size() + 1 > this.maxSize) {
    			this.triggerEviction();
    		}
    		
    		//*************************
    		//  LRU MECHANISM / LFU FREQUENCY QUEUES
    		//*************************
    		//now we need to get a sequence index for LRU mechanisms, 
    		//but we also need one for LFU frequency queues, so we do this part in any case
    		int lastIndex = 0;
    		Entry<Integer, PoolElement> entry = this.lruOrder.lastEntry();
    		if (entry != null) {
    			lastIndex = entry.getKey() + 1;
    		}
    		while (this.lruOrder.putIfAbsent(lastIndex, element) != null) {
    			//TODO: DRY
    			entry = this.lruOrder.lastEntry();
        		if (entry != null) {
        			lastIndex = entry.getKey() + 1;
        		}
    		}
    		element.setUseSequence(lastIndex);
    		
    		//*************************
    		//  LFU MECHANISM
    		//*************************
    		if (this.evictionMethod.equals(EvictionMethod.LFU)) {
    			//increment the use count for LFU mechanisms
    			element.incrementUseCount();

    			ConcurrentNavigableMap<Integer, PoolElement> frequencyQueue = 
    					new ConcurrentSkipListMap<Integer, PoolElement>();
    			frequencyQueue.put(element.getUseSequence(), element);
    			while (true){
    				Map<Integer, PoolElement> previousQueue = 
    						this.lfuOrder.putIfAbsent(element.getUseCount(), frequencyQueue);
    				if (previousQueue == null) {
    					break;
    				}
    				//synchronized block necessary to make sure it is not removed from 
    				//lfuOrder before we add element to it.
    				synchronized(previousQueue) {
    					if (previousQueue.isEmpty()) {
    						//if the previousQueue is empty, it means it was removed 
    						//(or about to be removed) from lfuOrder 
    						//before we had a chance to add element to it. 
    						//So, let's try again. 
    						//(actually, previousQueue could be emptied before being removed 
    						//from lfuOrder, but a lock will be obtained on it to check atomically 
    						//that it is empty before removing it, so it is equivalent; 
    						//worst case scenario we will have a few loops to wait for previousQueue 
    						//to be actually removed)
    						continue;
    					}
    					//otherwise, thanks to the synchronized block, we are sure 
    					//that another thread could not empty and remove it from lfuOrder now.
    					//Reference the element based on its use sequence (LRU mechanism 
    					//inside the frequency queues)
    					if (previousQueue.put(element.getUseSequence(), element) != null) {
    						throw log.throwing(new AssertionError("The sequence index " + 
    								element.getUseSequence() + " was not unique in a frequency queue, " +
    								"while sequence index should be unique in a given pool."));
    					}
    					break;
    				}
    			} 
    		}
        }
        //inform the PoolMonitor 
        PoolMonitor.updatePoolSize(this, this.elementCount.getAndIncrement(), 1);
        
        return log.exit(null);
    }

    /**
     * Remove a <code>PoolElement</code> from this <code>Pool</code>, 
     * depending on the eviction method defined at instantiation of this pool, 
     * and call <code>release</code> on it.
     * 
     * @throws ReleaseException 	If an error occurred while releasing the 
     * 								<code>PoolElement</code>. 
     */
    protected void triggerEviction() throws ReleaseException {
    	log.entry();
    	//defining the number of elements to remove
    	int toRemove = (int) Math.ceil(this.evictionFactor * this.elementCount.get());
    	log.debug("Evicting {} elements by {} method...", toRemove, this.evictionMethod);
    	for (int i = 0; i < toRemove; i++) {
    		if (this.evictionMethod == EvictionMethod.LRU) {
    			this.releaseLRU();
    		} else if (this.evictionMethod == EvictionMethod.LFU) {
    			this.releaseLFU();
    		}
    	}
    	log.debug("Eviction done.");
    	log.exit();
    }
    /**
     * Remove the least recently added <code>PoolElement</code> from this <code>Pool</code>, 
     * and call <code>release</code> on it.
     * 
     * @throws ReleaseException 	If an error occurred while releasing the 
     * 								LRU <code>PoolElement</code>. 
     */
    private void releaseLRU() throws ReleaseException {
    	log.entry();
        log.debug("Remove least recently used element from pool {}.", this); 
        
        Entry<Integer, PoolElement> entry = this.lruOrder.firstEntry();
        if (entry != null) {
        	PoolElement element = entry.getValue();
        	if (element != null) {
        		element.release();
        	}
        }
        
        log.exit();
    }
    /**
     * Remove the least frequently used <code>PoolElement</code> from this <code>Pool</code>, 
     * and call <code>release</code> on it.
     * 
     * @throws ReleaseException 	If an error occurred while releasing the 
     * 								LFU <code>PoolElement</code>. 
     */
    private void releaseLFU() throws ReleaseException {
    	log.entry();
        log.debug("Remove least frequently used element from pool {}.", this); 
        
        Entry<Integer, ConcurrentNavigableMap<Integer,PoolElement>> entry = 
        		this.lfuOrder.firstEntry();
        if (entry != null) {
        	Entry<Integer, PoolElement> frequencyEntry = entry.getValue().firstEntry();
        	if (frequencyEntry != null) {
        		PoolElement element = frequencyEntry.getValue();
        		if (element != null) {
        			element.release();
        		}
        	}
        }
        
        log.exit();
    }

    /**
     * Call {@link PoolElement#release()} on each <code>PoolElement</code> 
     * hold by this <code>Pool</code>, clear the <code>Pool</code>, 
     * and remove it from the <code>PoolMonitor</code> control.
     * 
     * @throws ReleaseException 	If an error occurred while releasing the 
     * 								<code>PoolElement</code>s in this <code>Pool</code>. 
     */
    public void close() throws ReleaseException
    {
    	log.entry();
    	
    	//to avoid ConcurrentModificationException
    	Collection<PoolElement> shallowCopy = 
    			new ArrayList<PoolElement>(this.poolContent.values());
    	for (PoolElement element: shallowCopy) {
    		element.release();
    	}
        this.poolContent.clear();
        this.lruOrder.clear();
        this.lfuOrder.clear();
        this.elementCount.set(0);
        log.debug("The pool {} has been unregistred", this);
        
        log.exit();
    }
    
    @Override
    public String toString() {
    	return super.toString() + " - element count: " + this.size();
    }

}
